﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
    class P0029 : IProblem
    {

        public void Run()
        {
            var s = new Solution();
            var list = new List<(int,int)>
            {
                //(1,1),
                //(2,1),
                //(3,1),
                //(4,3),
                //(5,2),
                //(7,-3),
                //(1,1),
                //(-2147483648,-1),
                //(2147483647,1),
                //(2147483647,2),
                (-2147483648,-3)
            };
            foreach (var v in list)
            {
                var startTime = DateTime.Now;
                var result = s.Divide(v.Item1, v.Item2);
                var endTime = DateTime.Now;

                Console.WriteLine(string.Format("input:{0} output:{1} useTime:{2}", string.Format("({0},{1})", v.Item1, v.Item2), result, (endTime - startTime).TotalMilliseconds));
            }
        }

        public class Solution
        {
            public int Divide(int dividend, int divisor)
            {
                int t = -1;
                int limit = 0;
                bool isNegative = divisor >= 0 ^ dividend >= 0;
                var r = -1;
                if (dividend == int.MinValue || divisor == int.MinValue)
                {
                    if (dividend == int.MinValue && divisor == -1)
                        return int.MaxValue;
                    if (dividend == int.MinValue && divisor == int.MinValue)
                        return 1;

                    if (dividend == int.MinValue)
                    { 
                        t = int.MaxValue;
                        limit = -1;
                    }
                    //只有除数为最小值
                    if (divisor == int.MinValue)
                        return 0;

                    divisor = Math.Abs(divisor);
                }
                else
                {
                    if (Math.Abs(divisor) > Math.Abs(dividend))
                    {
                        return 0;
                    }
                    t = Math.Abs(dividend);
                    divisor = Math.Abs(divisor);
                }

                int curDivisor = divisor;
                int zhishu = 1;
                while (t >= limit)
                {
                    if (t > divisor * 2 && divisor < int.MaxValue >> 1)
                    {
                        divisor = divisor << 1;
                        zhishu++;
                    }
                    while (t < divisor && zhishu > 1)
                    {
                        zhishu--;
                        divisor = divisor >> 1;
                    }
                    r += 1 << (zhishu - 1);
                    t -= divisor;
                  
                }

                return r * (isNegative ? -1 : 1);
            }
        }
    }
}
